package com.chenken;

/**
 *	上楼梯-动态规划
 *  楼梯有n阶台阶,每次往上走1步,或每次往上走2步，求走完n阶台阶一共有多少种走法?
 *  
 *	假设n阶台阶有f(n)种走法,第1步有2种走法
 *		如果第1步上1阶,那就还剩n-1阶, 共f(n-1)种走法
 *		如果第1步上2阶,那就还剩n-2阶,共f(n-2)种走法
 *	所以f(n) = f(n-1) + f(n-2)
 *
 *	状态转移方程	f(n) = f(n-1) + f(n-2)
 *	
 */
public class ClimbStairs {

	/**
	 * 	状态dp[n]	是走完n阶楼梯的走法
	 * @param num
	 * @return
	 */
	private static int climbStairs(int num) {
		if(num <= 0) return 0;
		
		int dp[] = new int[num+1];
		dp[1] = 1;
		dp[2] = 2;
		for(int i = 3;i <= num;i++) {
			//	状态转移方程
			dp[i] = dp[i-1] + dp[i-2];
		}
		return dp[num];
	}
	
	public static void main(String[] args) {
		int num = 5;
		System.out.println(climbStairs(num));
	}


}
